\documentclass{article}

\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[pdftex]{graphicx,color}

\usepackage[section]{placeins}

\usepackage{listings}
\lstset{language=C++,breaklines=true}

%configuracion de headers y footers
\usepackage{fancyhdr}
\pagestyle{fancy}
\renewcommand{\subsectionmark}[1]{\markboth{}{\thesubsection\ \ #1}}
\lhead{Organización de Datos}
\chead{}
\rhead{\rightmark}
\lfoot{}
\cfoot{}
\rfoot{\thepage}

\author{Facundo Olano 87712\and Leandro Romero 88240\and Federico José Carrone 88371\and José Aizpun 85996}
\title{Organización de Datos}

\begin{document}

%enchufo la pagina del título a lo cabeza
\begin{titlepage}
\begin{center}
% logo
%\includegraphics[width=100mm]{img/erl}\\

\ \\ % force an empty line
% textsc is small caps
\textsc{\Large
%
Facultad de Ingeniería\\
Universidad de Buenos Aires\\
\ \\
Organización de Datos\\
\ \\}
%
% the title
%
{\huge \bfseries
Toolkit de almacenamiento de datos
\\}
\ \\
\ \\

\ \\
\ \\
\end{center}
\begin{Large}Integrantes:\end{Large}
\begin{center}


% split the page into two columns
% left column
\begin{minipage}{0.4\textwidth}
\begin{flushleft} \large
Facundo Olano\\
Leandro Romero\\
Federico José Carrone\\
José Aizpun\\
\end{flushleft}
\end{minipage}
%
% right column
\begin{minipage}{0.4\textwidth}
\begin{flushright} \large
87712\\
88240\\
88371\\
85996\\
% ensure vertical alignment with LHS
\footnotesize{\ }
\end{flushright}
\end{minipage}


\vfill % fill vertical space
%
% Bottom of the page
% \today is the compilation date
{\large \today}
%
\end{center}
\end{titlepage}

\tableofcontents
\clearpage

\section{Introducción}

Lograr almacenar grandes cantidades de informacion, y al mismo tiempo poder accederla de una forma rapida y eficiente no es una tarea trivial. El objetivo de este toolkit es encapsular esa dificultad y ofrecerle al usuario la posibilidad de almacenar grandes cantidades de datos, y permitirle acceder a los mismos de manera rapida y eficiente, sin que se preocupe por la utilizacion de buffers u ordenamiento de la informacion.

Para lograr este objetivo fue necesaria la utilizacion del lenguaje de programacion C++ dado que el diagrama UML de clases que se utilizo como base exigia la utilizacion de herencia multiple, que no encontramos en lenguajes mas amigables como JAVA. Por otro lado, este lenguaje nos permite realizar operaciones de mas bajo nivel que otros lenguajes, logrando mas eficiencia en las operaciones necesarias.

\section{Guía de uso del Toolkit}

\subsection{Adaptando objetos de dominio}

El primer paso para poder persistir objetos usando el Toolkit es el de adaptarlos para que cumplan la interfaz Dato (figura \ref{cod_dato}). Esto es importante puesto que es la manera que la API tiene de tratar uniformemente cualquier tipo de información que se pretenda serializar.

\begin{figure}[htb]
\centering
\lstinputlisting{src/Dato.h}
\caption{Dato.}
\label{cod_dato}
\end{figure}

El método \emph{serializar} debe almacenar toda la información del objeto que pretende persistirse en un
stringstream de C++ (más detalles de stringstreams pueden verse en \ref{s_streams} y \cite{iostreams}). El método \emph{hidratar} debe, a partir de un stringstream generado con \emph{serializar}, reconstruir la instancia del Dato.

Se pide adicionalmente un método \emph{clonar} de manera de poder realizar la construcción virtual de instancias del
objeto de domino\cite{clone}. Éste devolverá un puntero a una instancia nueva de esa clase, alocada en el heap.

Como en cualquier esquema de almacenamiento de información, cada unidad, en este caso el Dato, debe poder ser
identificada unívocamente respecto a las demás. Para esta tarea se utiliza la interfaz Clave (figura \ref{cod_clave}).
Cada operación provista por el Toolkit utilizará una instancia de clave asociada al Dato con el que se quiere trabajar.

\begin{figure}[htb]
\centering
\lstinputlisting{src/Clave.h}
\caption{Clave.}
\label{cod_clave}
\end{figure}

Además de los métodos \emph{serializar}, \emph{hidratar} y \emph{clonar}, análogos a los presentes en el Dato,
se deben implementar operadores de igualdad y comparación entre claves y datos. De esta forma, dada una clave
esta se podrá saber si es mayor o igual a otra clave, o si es mayor o igual a la clave que correspondería a un determinado dato.

El funcionamiento consistente del Toolkit depende en gran medida de la correcta implementación de las interfases anteriores. 
Particularmente, se supone que cada Dato diferente tendrá una Clave diferente, siendo de esta forma el operador de igualdad
de la Clave fundamental para realizar las búsquedas y los controles de unicidad en los recursos de almacenamiento.

\subsection{Usando recursos de almacenamiento}
Una vez adaptados los datos, todo el trabajo con la API ser realiza a través de una instancia de Recurso de Almacenamiento.
La figura \ref{cod_recurso} muestra su interfaz, compuesta por los métodos:

\begin{figure}[htb]
\centering
\lstinputlisting{src/Recurso.h}
\caption{Recurso de Almacenamiento.}
\label{cod_recurso}
\end{figure}

\begin{itemize}
\item guardarDato: Guarda el dato en el recurso de almacenamiento. Se debe pasar también la clave de ese dato, que se usa
para verificar su unicidad. Si la clave se encontraba almacenada previamente se arrojará una excepción. Para modificar claves previamente almacenadas, debe usarse el método \emph{actualizarDato}.

\item recuperarDato: Busca en el recurso la clave cuyo dato es especificado. En caso de encontrarse ese dato (fue almacenado guardado previamente en el recurso), se devuelve \emph{true} y se hidrata la instancia pasada con su contenido. 
Si el dato no es encontrado, se devuelve \emph{false}.

\item actualizarDato: Reemplaza el contenido del dato asociado a la clave especificada en el recurso, por el 
pasado en la nueva instancia de dato. Si no se encuentra un dato asociado a esa clave en el recurso, se lo agrega
como nuevo (equivalente a \emph{guardarDato}).

\item eliminarDato: Se retira del almacenamiento el dato cuya clave es especificada, y se lo devuelve hidratando 
la instancia pasada. En caso de que el dato no se encuentre, no se altera el recurso.
\end{itemize}

%TODO agregar lo de la busqueda secuncial si se hace

\subsection{Construyendo recursos de almacenamiento}
Para facilitar la construcción y configuración de las instancias de Recurso de Almacenamiento descriptas en la sección
anterior, la API provee una Fábrica de Recursos de Almacenamiento, cuya interfaz se describe en la figura \ref{cod_fabrica}.

\begin{figure}[htb]
\centering
\lstinputlisting{src/Fabrica.h}
\caption{Fábrica de Recursos de Almacenamiento.}
\label{cod_fabrica}
\end{figure}

La Fábrica implementa el patrón de diseño Singleton\cite{gof95}, por lo que los llamados a sus métodos se realizan
estáticamente, de la forma:

\begin{lstlisting}
Toolkit::RecursoAlmacenamiento *recurso = Toolkit::FabricaRecursos::instancia().recursoBuffer(Toolkit::TEXTO, Toolkit::A_BLOQUES, 150);
\end{lstlisting}

Cada método aplica un esquema distinto para construir el Recurso de Almacenamiento, a saber:

\begin{itemize}
\item recursoBuffer: El recurso se configura con un almacenamiento no persistente en memoria.

\item recursoArchivo: El recurso se configura con un almacenamiento persistente en disco. Se debe especificar la ruta
y nombre del archivo a ser usado como almacenamiento.

\item recursoEscrituraDirecta: Se utiliza un almacenamiento en Archivo, acompañado por un Buffer para agilizar las lecturas,
aplicando una política de escritura directa. Se debe especificar la ruta
y nombre del archivo a ser usado como almacenamiento.

\item recursoEscrituraDiferida: Se utiliza un almacenamiento en Archivo, acompañado por un Buffer caché aplicando una política de
escritura diferida con LRU. Se debe especificar la ruta,
nombre del archivo a ser usado como almacenamiento y el tamaño con el que se quiere crear el Buffer.

\item recuperarRecurso: Se recupera un recurso de almacenamiento previamente construido; para haberse persistido, 
éste necesariamente debió ser construido con un archivo, ya sea mediante \emph{recursoArchivo} o \emph{recursoBufferArchivo}.
Para reconstruir el recurso, es necesario especificar la ruta y nombre de archivo con que fue creado originalmente, 
así como el tipo de serialización que se eligió.
\end{itemize}

El tamaño de unidad requerido en los métodos será usado para serializar los datos que se almacenene, así como la metadata
que necesita acompañarlos para poder ser recuperados (que se puede estimar en 2 bytes para cada componente). 
Entonces si el usuario pretende almacenar datos de 100 bytes en registros de longitud fija, un tamaño de unidad apropiado sería de 102 bytes. %esto apesta bastante encapsularlo en la fabrica

La ruta donde crear los recursos debe ser dada en el mismo formato usado en el shell de Linux. Por ejemplo, para crear
un almacenamiento en una archivo \emph{archivo.txt}, en el directorio \emph{recursos} (subdirectorio de aquel desde
donde se ejecuta el programa), entonces los valores de ruta y nombre serán específicamente: ruta = ``recursos/'', 
nombre = ``archivo.txt''.

Las opciones de configuración aplicables a la Fábrica se describen en la tabla \ref{t_opciones}. Las indexaciones son solo usadas sobre los archivos.

\begin{table}[h]
\centering
\begin{tabular}{|c|c|p{4cm}|}
\hline
Tipo	& Valor	& Descripción	\\
\hline
TipoSerializacion			& BINARIO						& Serializacion en formato binario	 \\
							& TEXTO							& Serializacion en formato binario	 \\

\hline
UnidadAlmacenamiento		& A\_REGISTROS					& Organización de almacenamientos en registros	 \\
							& A\_TEXTO						& Organización de almacenamientos en registros de texto\\
							& A\_BLOQUES					& Organización de almacenamientos en bloques de registros\\
							& A\_BLOQUES\_COMPRESOS			& Organización de almacenamientos en bloques de registros, aplicando compresión\\
							
\hline
TipoIndexado				& SIN\_INDEXADO					& No se aplica indexación sobre el almacenamiento primario	 \\
							& HASHING\_EXTENSIBLE			& Se aplica un índice con organización directa mediante dispersión extensible \\
							& B\_SHARP						& Se aplica un índice con organización balanceada mediante un árbol B\#		 \\

\hline

\end{tabular}
\caption{Opciones de configuración.}
\label{t_opciones}
\end{table}

\subsection{Ejemplo}
A modo de ejemplo del uso del Toolkit, se describe paso a paso su aplicación para el almacenamiento de Datos de alumnos.
Se parte entonces de un objeto de dominio Alumno, cuya interfaz se muestra en la figura \ref{cod_alumno1}.
Como se explicó en secciones anteriores, se hace necesario adaptar esa clase a la del Dato del Toolkit, resultando
la clase descripta en las figuras \ref{cod_alumno2} y \ref{cod_alumno3}. Se eligió realizar serializaciones en formato de texto, facilitadas
por algunas funciones auxiliares del toolkit para el manejo de stringstreams (pueden encontrarse en el módulo ``funciones.h'') que no hacen más de encapsular llamados a \emph{write} y \emph{read} de los valores que se desean persistir.

\begin{figure}[htb]
\centering
\lstinputlisting{src/Alumno1.h}
\caption{Objeto de dominio Alumno.}
\label{cod_alumno1}
\end{figure}

\begin{figure}[htb]
\centering
\lstinputlisting{src/Alumno2.h}
\caption{Objeto de dominio Alumno, adaptado a la interfaz Dato.}
\label{cod_alumno2}
\end{figure}

\begin{figure}[htb]
\centering
\lstinputlisting{src/Alumno3.h}
\caption{Objeto de dominio Alumno, adaptado a la interfaz Dato. (continuación)}
\label{cod_alumno3}
\end{figure}

El paso siguiente es el de construir una clave para el Dato creado. Se elije usar el padrón como el identificador
único del alumno, resultando la implementación de ClaveAlumno de las figuras \ref{cod_clavealumno1} y \ref{cod_clavealumno2}.

\begin{figure}[htb]
\centering
\lstinputlisting{src/ClaveAlumno1.h}
\caption{Clave para el Dato Alumno. (continuación)}
\label{cod_clavealumno1}
\end{figure}

\begin{figure}[htb]
\centering
\lstinputlisting{src/ClaveAlumno2.h}
\caption{Clave para el Dato Alumno. (continuación)}
\label{cod_clavealumno2}
\end{figure}

Por último se genera un recurso de almacenamiento a través de la fábrica y se comienza su utilización;
se elige una estrategia de almacenamiento en Bloques de 150 bytes de tamaño, y el uso de dos almacenamientos, Archivo y Buffer, uno de ellos indexado por hashing extensible (figura \ref{cod_ejemplo}). El archivo de trabajo se generará en ``pruebaRecurso.txt''.

\begin{figure}[htb]
\centering
\lstinputlisting{src/Ejemplo.h}
\caption{Construcción y utilización del recurso de almacenamiento de alumnos.}
\label{cod_ejemplo}
\end{figure}

\subsection{Archivos generados por la aplicación}
Suponiendo que se crea un almacenamiento en un archivo de nombre \emph{miRecurso.txt}, la aplicación generará los siguientes archivos para su trabajo:

\begin{itemize}
\item miRecurso.txt: archivo del almacenamiento, acá se guardaran los datos pasados al recurso.
\item miRecurso.txt.nul: mapa de nulidad del almacenamiento, utilizado para controlar la fragmentación externa del
archivo (véase \ref{s_frag_ext}).
\item miRecurso.txt.frag: índice de espacio libre en las unidades del alamacenamiento, en caso de que se organice en bloques
de registros. Sirve para controlar la fragmentación interna (véase \ref{s_frag_int}).
\item miRecurso.txt.p: encabezado del almacenamiento, para guardar metadata. Solo se crea en caso de que el archivo serialice a texto.
\end{itemize}

\subsection{Excepciones}
A continuación se listan las distintas excepciones que puede arrojar el Recurso de Almacenamiento, y sus posibles causas.

\begin{itemize}
\item ClaveDuplicadaException: Esta excepción se lanza cuando se intenta guardar en un almacenamiento un nuevo Dato, cuya clave coincide con la de otro almacenado previamente.

\item DesbordeDeDatoException: Se lanza cuando se intenta persistir un dato cuya serialización excede el tamaño de unidad
con que se configuró el almacenamiento al ser creado.

\item ArchivoInexistenteException: Se arroja al intentar recuperar un recurso de almacenamiento que no está presente
en la dirección especificada por el controlador.

\item NoSePuedeCrearArchivoException: Se lanza si el sistema operativo no permite al Toolkit la creación de un archivo.
\end{itemize}

\section{Arquitectura general del Toolkit}

El diagrama de la figura \ref{diag1} muestra las principales entidades del sistema, y como interactúan entre sí.
En la mayoría de los casos se trata de clases abstractas, cuyas especializaciones dan alternativas
al comportamiento del Toolkit.

\begin{figure}[htb]
\centering
\includegraphics[scale=0.4]{img/Diagram1}
\caption{Entidades principales del Toolkit.}
\label{diag1}
\end{figure}

La fábrica de recursos de almacenamiento provee una interfaz simplificada para la generación de instancias de
RecursoAlmacenamiento, clase escencial del Toolkit, que permite persistir datos en un almacenamiento.
Desde el punto de vista del usuario, el uso del sistema se reduce a generar un recurso con la fábrica y
utilizar sus métodos para trabajar con objetos de dominio, que deberán ser herederos de la calse Dato, y
que deben poder ser identificados con un objeto Clave (este último no se muestra en el diagrama).

A continuación se describen en más detalle las responsabilidades e incumbencias de cada una de esas entidades.

\subsection{Dato y Clave}
Las clases Dato y Clave son las herramientas que usa el toolkit para poder manipular abstractamente cualquier
objeto que el controlador pretenda almacenar. Esto es, para poder persistir elementos de una clase A, 
ésta debe implementar la interfaz Dato, y deberá existir una clase ClaveA, que implemente la interfaz
Clave de tal manera que permita identificar unívocamente cada instancia de A.

Se tomo como premisa ser lo menos intrusivo posible con los objetos de dominio del usuario, con lo cual la
interfaz Dato solo exige métodos para serializar e hidratar usando stringstreams (véase \ref{s_streams}),
y un método adicional para clonar datos.

Para la Clave, además de los métodos presentes en Dato, se pide la implementación de comparadores con
otras claves y con datos. La arquitectura interna del Toolkit depende fuertemente de la correcta 
implementación de esos métodos, puesto que son el único medio que posee para realizar controles de unicidad, 
ordenamientos, identificaciones en las búsquedas, etc.

\subsection{Componente}
Si bien es cierto que estrictamente los archivos son siempre secuencias de bits, resulta útil organizarlos
en estructuras lógicas como registros o bloques, cuando se analiza al archivo 
(o más generalmente a cualquier almacenamiento) desde un punto de abstracción más alto\cite{folk98}.

Los datos se representarán en almacenamiento como registros que alternativamente pueden agruparse en forma
de bloques para su lectura y escritura. Estas entidades lógicas se represntan en el Toolkit a través de componentes,
como se describe en el diagrama de la figura \ref{diag_comp}. El Bloque implementa el patrón Composite\cite{gof95}.

\begin{figure}[htb]
\centering
\includegraphics[scale=0.4]{img/DiagComp}
\caption{Jerarquía de componentes.}
\label{diag_comp}
\end{figure}

Tales componentes, que son administrados por una estrategia de almacenamiento (véase \ref{s_estr_alm}), se
utilizan como paso previo a la interacción con los almacenamientos, para serializar los datos
con la metadata necesaria para que puedan ser recuperados consistentemente por el sistema. 
A su vez, su utilización permite garantizar al almacenamiento que las unidades que debe manipular serán
serializaciones de tamaño fijo, ya sean registros de longitud fija o registros de longitud variable
contenidos por bloques de longitud fija.

El bloque compresor es una especialización del bloque, que aplica un algoritmo de compresión a las serializaciones
que realiza. La compresión se discute en detalle en \ref{compresion}.

\subsection{Almacenamiento}
El Almacenamiento es una clase pasiva, que agrega una capa de abstracción sobre las herramientas
de bajo nivel de C++ para el manejo archivos y buffers. Posee métodos para almacenar y recuperar
datos serializados en unidades de longitud fija, permitiéndo de esta forma su acceso en forma aleatoria.

Las dos variantes de almacenamiento son Archivo, para almacenar información en disco, y Buffer, para
almacenarla en memoria. La única diferencia entre ambas, obviando evidente mejora de la velocidad
de trabajo con el Buffer, es que el archivo contempla la necesidad de reservar un espacio para 
metadata en su encabezado.

Sin embargo, la variante de Almacenamiento $Buffer$ esta diseñada para que su uso no se vea limitado al uso de memoria convencional. Hoy en dia existen dispositivos de almacenamiento de datos masivos con velocidades de acceso similares a las obtenidas por la memoria principal de sistema (ej, memoria RAM), como pueden ser los discos de estado solido o simplemente tarjetas $flash$. Como ejemplo de esta tendencia tenemos al sistema de archivos utilizado en Solaris 10, el $Solaris ZFS$ \cite{SolarisZFS}, que puede ser configurado para utilizar discos de estado solido a modo de buffer, optimizando asi sus tiempos de accesso de manera exponencial. Por otro lado, tenemos la posibilidad de utilizar la RAM como $RAM-Disks$, es decir, utilizar porciones de la RAM como si fuera un medio de almacenamiento masivo para acelerar el acceso a archivos de uso frecuente. Si bien este tipo de almacenamiento no es persistente a traves de los reinicios, esto no es un problema para los grandes servidores donde estos eventos rara vez ocurren gracias a inumerables medidas de redundancia en fuentes de alimentacion y UPS. Un ejemplo de uso de esta tecnica es el sistema operativo $Amiga OS$\cite{AmigaOS}

La limitacion de este tipo de almacenamiento respecto de la memoria principal de sistema es que no podemos guardar objetos como lo hacemos en esta ultima. La solucion a esta limitacion es simplemente guardar la informacion serializada en cualquier tipo de buffer que se utilice. La desventaja es la necesidad de $hidratar$ la informacion cada vez que es recuperada, pero siendo estas porciones pequeñas, y la operacion llevada a cabo en memoria principal, el impacto es menor.

\subsection{Estrategia de Almacenamiento}
\label{s_estr_alm}
La Estrategia de almacenamiento es una clase de mayor nivel que el Almacenamiento y es, de hecho, la que realiza
todas las transacciones con éste. Su principal responsabilidad es la de encapsular la organización de los datos
en Componentes dentro del almacenamiento, en forma transparente al resto de las clases del Toolkit.

A grandes rasgos, la tarea de la estrategia es la de tomar un dato, organizarlo en un componente, serializarlo 
y almacenarlo, o el proceso inverso, en caso de querer recuperar un dato almacenado anteriormente.

Las especializaciones propuestas para la estrategia de almacenamiento son las de organización en Registros, 
y organización en Bloques de Registros. Si se quisiera soportar un nuevo tipo de organización, por ejemplo
bloques de bloques de registros, bastaría con implementar una nueva especialización de la estrategia.

\subsection{Recurso de Almacenamiento}
El Recurso de Almacenamiento es la clase principal del Toolkit desde la perspectiva del controlador. 
Sin embargo, visto desde la arquitectura interna, se limita a contener los distintos elementos requeridos
para el almacenamiento de un dato determinado (almacenamientos, estrategias, índices), y delega todo su 
comportamiento a la Estrategia de Recurso.

El recurso puede tener un almacenamiento primario (obligatorio) y uno secundario (opcional). Si bien no hay 
restricciones en cuanto a la especialización de Almacenamiento que se utiliza para implementar cada uno,
se presupone que el almacenamiento secundario será de acceso más veloz que el primario, y que de haber un índice,
el almacenamiento que se indexa será el primario.

Típicamente, cuando se usen dos almacenamientos, el primario será un Archivo y el secundario un Buffer. Este es
el esquema previsto por la fábrica de recursos de almacenamiento, y el que asumen las estrategias de recurso de
 dos almacenamientos.

\subsection{Estrategia de Recurso}
Las especializaciones de ésta clase implementan, con diferentes políticas, el comportamiento del Recurso de almacenamiento,
con una interfaz indéntica a la de esa clase.

La utilidad de separar esos algoritmos es la de poder variar la manera en que se utilizan las distintas combinaciones
de almacenamientos e índices que pueden presentarse en el Recurso de Almacenamiento.

Actualmente se provee una especialización para recursos de un solo almacenamiento y otra para recursos de dos almacenamientos, con política de escritura directa. La primera presume que sólo el almacenamiento primario existe,
y por ende realiza todas las tareas exclusivamente en él. Las búsquedas se hacen a través del índice de existir éste, secuencialmente en caso contrario. La segunda realiza todas las modificaciones en ambos almacenamientos; para las consultas, 
se intenta primero una búsqueda secuencial en el almacenamiento secundario, y de no encontrar resultados se intenta
con el primario (de nuevo, usando el índice si está disponible).

Sería natural proveer otras políticas para el manejo de dos almacenamientos, por ejemplo escritura diferida, mediante nuevas especializaciones de la estrategia de recurso.

\subsection{Índice}
Los índices permiten el acceso a los datos mediante una cantidad limitada de consultas al almacenamiento, evitando la necesidad de realizar costosas búsquedas secuenciales, o imponer organizaciones particulares en los archivos de datos.
Se implementan con organizaciones especiales de almacenamientos cuyos datos consisten en las claves de los registros
y sus posiciones en el archivo que se indexa.

Se optó el abstraer por completo a los almacenamientos de la estrategia de indexación utilizada por el recurso.
Esto implica que en ningún caso la organización de los datos en el archivo se ve afectada por el uso de un tipo 
determinado de índices.

Las estrategias de indexación provistas por el Toolkit son balanceada, a través de un árbol B\#, y directa, a través
de Hashing Extensible\cite{folk98}. Las implementaciones se discuten en detalle en \ref{s_indices}.

\subsection{Interacción entre componentes}

Para clarificar las incumbencias de cada clase, se muestra la secuencia de trabajo en los casos de alta de un nuevo dato, 
y de consulta de un dato almacenado previamente. Por simplicidad, se supone que hay un solo almacenamiento, y que está indexado.

Para dar de alta un nuevo Dato, el controlador se lo pasa al Recurso de Almacenamiento junto con su Clave asociada.
Este delega el mensaje a su Estrategia de Recurso, la cual empieza por verificar la unicidad de la clave, buscándola
en el índice. Como la clave no es encontrada, el dato es ahora pasado a la Estrategia de Almacenamiento, junto
con el almacenamiento primario en el que se debe guardar. La Estrategia de Almacenamiento construye un componente,
le inserta el dato y lo serializa. Por último le pasa esa serializacion al almacenamiento, que lo guarda en una 
posición que devuelve como resultado. Al retomar el control, la Estrategia de Recurso notifica el alta de la Clave y la posición al índice. La secuencia se ilustra en el diagrama de la figura \ref{diag_alta}.

\begin{figure}[htb]
\centering
\includegraphics[scale=0.35]{img/seq1}
\caption{Alta de un dato.}
\label{diag_alta}
\end{figure}

Para realizar una búsqueda, se pasa al Recurso la clave por la que debe buscar. Al recibir el mensaje, la
Estrategia de Recurso consulta al índice por la clave pasada, recibiendo como resultado una posición de su 
almacenamiento primario. Se llama a continuación a la Estrategia de Almacenamiento con el primario, y la posición
en la que debe buscar la clave pedida. Ésta pide al almacenamiento la serialización guardada en esa posición, 
hidrata el componente correspondiente, y extrae finalmente el dato que se devuelve al controlador.
La figura \ref{diag_consulta} muestra la secuencia.

\begin{figure}[htb]
\centering
\includegraphics[scale=0.35]{img/seq2}
\caption{Consulta de un dato.}
\label{diag_consulta}
\end{figure}

\section{Notas de implementación}

\subsection{Manejo de las serializaciones: stringstreams}
\label{s_streams}

\subsection{Implementación de los almacenamientos: iostreams}
La idea básica de las especializaciones de la clase almacenamiento es la de proveer una interfaz de persistencia de
unidades independiente del medio en que ésta se realice. De ésta forma, para el usuario, las únicas diferencias entre
un buffer en memoria y un archivo en disco, son la velocidad de respuesta y el hecho de que el archivo es recuperable
tras terminar el programa. 

Para cumplir elegantemente este objetivo, se aprovecharon las facilidades de la biblioteca iostream de C++ \cite{iostreams}, realizando todas
la operaciones en la clase almacenamiento sobre una instancia de \emph{iostream}, que se crea en cada subclase según corresponda:
un \emph{stringstream} para el buffer y un \emph{fstream} para el archivo.

Todo el comportamiento específico de las especializaciones quda en constructores y destructores, con métodos adicionales en el archivo para escribir
un encabezado con metadata.

% \subsection{Abstracción del medio de almacenamiento: wrappers}
%TODO completar esto

%\subsection{Serialización e hidratación de componentes}

%\subsection{Serialización en forma de texto}

\subsection{Control de fragmentación externa}
\label{s_frag_ext}
la fragmentación externa en archivos (o buffers) se refiere a los espacios inutilizados que quedan entre los datos almacenados, a causa
de eliminaciones o realocaciones de registros\cite{folk98}. La mayor parte del problema queda resuelto por el hecho de trabajar con unidades
de almacenamiento de tamaño fijo (en nuestro caso se trata de registros de longitud fija o bloques fijos de registros variables), basta
establecer una política para reusar los espacios vacíos que se producen al eliminar una unidad.

La técnica utilizada es la de realizar eliminaciones lógicas de las unidades, manteniendo un mapa de nulidad en memoria, esto es, una lista
de las direcciones que corresponden a espacios vacíos en el archivo: al realizar una eliminación se agrega la posición a la lista, al
guardar un dato se intenta reusar cualquiera de esas posiciones. Cuando el archivo se destruye al cerrar el sistema, la lista de posiciones
vacías se persiste en un archivo auxiliar para ser recuperada al reconstruir el almacenamiento.

% \subsection{Control de fragmentación interna}
\label{s_frag_int}
%TODO completar esto


\section{Índices}
\label{s_indices}

\subsection{Indice con Hashing extensible}

\subsubsection{Origen y mecanica del indice por $Hashing$ extensible}

Un indice por hashing extensible es una variacion del indice por hashing tradicional. Para entender el indice por hashing extensible, primero es necesario tener una nocion basica sobre el indice por hashing tradicional.

Un indice por hashing tradicional utiliza una tabla de tamaño fijo donde guardara las claves y sus correspondientes posiciones de almacenamiento y se basa en obtener un $hash$ a partir de la clave a indexar, y guardar el par clave-posicion en la posicion de la tabla que corresponda con los primeros (o ultimos) n-bits del $hash$, segun el tamaño de la tabla utilizada. Para manejar los desbordes hay distintas variaciones que van desde simplemente utilizar la siguiente posicion disponible de la tabla de $hashes$ hasta la utilizacion de listas enlazadas direccionados desde la tabla, que iran creciendo a medida que se reiteren los desbordes.

Sobre las base de un indice por $hashing$ tradicional se construye la idea de un indice por $hashing$ extensible. Al igual que una de las variantes del indexado por $hashing$ tradicional, el indexado por $hashing$ extensible utiliza bloques para guardar los pares calve-posicion, direccionando a estos bloques a traves de la tabla de $hashes$ que a partir de ahora llamaremos $directorio$. Si bien los pares clave-posicion se guardan en forma desordenada dentro de los bloques, que llamaremos $cubas$, se procura mantener siempre en cada cuba solo las claves cuyos $hashes$ coinciden con el direccionamiento que recibe la cuba que las aloja.

La principal diferencia entre este tipo de indices y los tradicionales radica en la reaccion ante los desbordes, pudiendo lograr esto gracias a que su directorio de $hashes$ no es de tamaño fijo, sino dinamico. Esto implica que la cantidad de bits del $hash$ contemplados para direccionar las cubas es tambien variable, y sera acorde al tamaño del directorio. Llamaremos a esta cantidad de bits, la "profundidad" del directorio. Por otro lado, puede haber mas de una referencia a una cuba en el directorio, mientras las claves que aloja la cuba correspondan con las posiciones direccionadas desde el directorio. En esta situacion se dice que la cuba tiene menor profundidad que el directorio. Se puede ver un ejemplo del directorio direccionando algunas cubas en la figura \ref{cod_Ejemlpos_Hashing_1}

\begin{figure}[htb]
\centering
\includegraphics[scale=0.3]{img/Hashing/Ejemlpos_Hashing_1.png}
\caption{Estado original del indice antes de las eliminaciones.}
\label{cod_Ejemlpos_Hashing_1}
\end{figure}

Cuando una cuba se desborda, y el directorio tiene solo una referencia a esta cuba, este duplica su tamaño y todas sus referencias a cada cuba. En esta situacion, el directorio obtiene al menos dos referencias por cada cuba del indice. Gracias a esto, tenemos la posibilidad de utilizar una de las referencias sobrantes generada para la cuba desbordada para direccionar a una nueva cuba con la cual se repartiran los pares clave-posicion segun el direccionamiento correspondiente de los hashes. Esta operacion la denominaremos "division" de una cuba y podemos ver un ejemplo del proceso completo desde la figura \ref{cod_Ejemlpos_Hashing_7} a la figura \ref{cod_Ejemlpos_Hashing_8} cuando la cuba A es desbordada.
\begin{figure}[htb]
\centering
\includegraphics[scale=0.3]{img/Hashing/Ejemlpos_Hashing_7.png}
\caption{Se inserto una clave a la cuba A, y fue necesaria una division resultando en la cuba E.}
\label{cod_Ejemlpos_Hashing_7}
\end{figure}
\begin{figure}[htb]
\centering
\includegraphics[scale=0.3]{img/Hashing/Ejemlpos_Hashing_8.png}
\caption{Se inserto otra clave a la cuba A, y fue necesaria una division de A, resultando en la cuba F y en la expansion del directorio.}
\label{cod_Ejemlpos_Hashing_8}
\end{figure}
Por otro lado, tambien puede ocurrir que cuando una cuba desborde, el directorio ya posea mas de una referencia a esta cuba, por anteriores expansiones del directorio. Esto implica que la cuba tenia una profundidad menor que la del directorio. En esta situacion, simplemente se divide la cuba y se la asocia a la mitad de las referencias del directorio que apuntaban a la cuba original, sin aumentar el tamaño del directorio. Como ejemplo de este proceso se puede ver la figura \ref{cod_Ejemlpos_Hashing_6} a la figura \ref{cod_Ejemlpos_Hashing_7} cuando la cuba A es desbordada. En ambos casos siempre se respetara el direccionado correspondiente por los $hashes$ que aloje cada cuba.

\begin{figure}[htb]
\centering
\includegraphics[scale=0.3]{img/Hashing/Ejemlpos_Hashing_6.png}
\caption{Estado original del indice antes de las inserciones.}
\label{cod_Ejemlpos_Hashing_6}
\end{figure}

Tambien puede ocurrir el proceso inverso que denominamos "combinacion" de cubas, y/o "colapsar" el directorio. Estas situaciones se dan cuando se eliminan pares clave-posicion de alguna cuba, permitiendo que esta se combine con alguna cuba aledaña. Esta combinacion solo es posible si la cuba aledaña tiene la misma profundidad que la cuba en cuestion, y es necesario que la cantidad de informacion de ambas quepa en una sola cuba. Si estos requisitos se dan, se procede a una combinacion se cubas, pudiendose considerar que la cuba resultante no qude completamente llena sino por debajo de un determinado umbral para no arriesgarnos a un inmediato rebalse. Vemos un ejemplo de este proceso comenzando por la figura \ref{cod_Ejemlpos_Hashing_1}, a la figura \ref{cod_Ejemlpos_Hashing_2} cuando se combinan las cubas C y D.
\begin{figure}[htb]
\centering
\includegraphics[scale=0.3]{img/Hashing/Ejemlpos_Hashing_2.png}
\caption{Se elimina una clave de C y queda espacio para combinarse con D.}
\label{cod_Ejemlpos_Hashing_2}
\end{figure}
Realizado esto, se procede a evaluar si gracias a esta combinacion estamos en condiciones de colapsar el directorio. Esto se logra si tenemos al menos 2 referencias de cada cuba en el directorio, en cuyo caso simplemente eliminamos la mitad de ellas, y reducimos el tamaño del directorio a la mitad. Esto se puede apreciar en la figura \ref{cod_Ejemlpos_Hashing_3} donde se ha colapsado el directorio.
\begin{figure}[htb]
\centering
\includegraphics[scale=0.3]{img/Hashing/Ejemlpos_Hashing_3.png}
\caption{Se colapsa el directorio, quedandonos con la mitad de las referencias.}
\label{cod_Ejemlpos_Hashing_3}
\end{figure}
A su vez, es posible que la cuba recientemente combinada, pueda ahora volver a combinarse con otra aledaña si esta cumple con las condiciones necesarias, como muestra la figura \ref{cod_Ejemlpos_Hashing_4} y otra vez como queda demostrado en la figura \ref{cod_Ejemlpos_Hashing_5}. Este proceso se repite tantas veces como sea necesario con el fin de reducir al maximo posible el directorio.
\begin{figure}[htb]
\centering
\includegraphics[scale=0.3]{img/Hashing/Ejemlpos_Hashing_4.png}
\caption{Aun nos queda lugar en la Cuba C-D para combinarse con la B.}
\label{cod_Ejemlpos_Hashing_4}
\end{figure}
\begin{figure}[htb]
\centering
\includegraphics[scale=0.3]{img/Hashing/Ejemlpos_Hashing_5.png}
\caption{El directorio vuelve a colapsarse.}
\label{cod_Ejemlpos_Hashing_5}
\end{figure}

\subsubsection{Ventajas y desventajas del indexado por $hashing$ extensible}
Almacenar grandes volúmenes de datos conlleva el problema de poder acceder rápidamente al componente que nos interesa. 
Si no existiera ningún tipo de indexado seria necesario recorrer todos los datos secuencialmente, o en el mejor de los 
casos realizar una búsqueda binaria si lográramos mantener los datos ordenados. En cualquier caso, implicaría una gran 
cantidad de accesos a disco.

Las implementaciones de indices elementales disminuyen notablemente la cantidad de accesos a disco necesarios para acceder 
a la información deseada. En el caso del indexado por $hashing$, estos accesos se logran reducir a solo un acceso a disco 
y otro al directorio (que pueda estar en memoria o en disco) que es en general mucho menos que cualquier otro tipo de 
indexado. A su vez, este tipo de indexado es comparable con el indexado por $hash$ simple. Este ultimo tiene la desventaja 
de tener tamaño fijo, lo que conlleva a que existan colisiones entre las claves a indexar y la necesidad de diseñar un 
algoritmo de búsqueda que contemple estas posibles colisiones, generando demoras en la búsqueda. Por otro lado, el indexado 
por $hash$ extensible no tiene este problema ya que cuando agota la capacidad de cada cuba simplemente la divide y la asocia 
al directorio.

Sin embargo, este tipo de indices tiene ciertas desventajas. Una de ellas es la necesidad de expandir el directorio cuando 
se necesita dividir las cubas y el directorio no es suficientemente grande como para direccionarlas. Esta expansión es una 
tarea extensa que puede necesitar de varios accesos al recurso de almacenamiento si el directorio no cabe en memoria 
principal. Otro problema es la división de las cubas cuando estas desbordan, que deriva en que por solo intentar insertar 
un solo par clave-posición, es necesario analizar y mover muchos mas registros entre las cubas divididas.

Por estos dos problemas es que toma importancia el equilibrio adecuado en el tamaño de la cuba. Si la cuba es demasiado 
grande, las eventuales divisiones de las misma se vuelve demasiado trabajosa y se pierde mucho tiempo en estos casos. Por 
otro lado, si la cuba es demasiado chica, los constantes desbordes de las cubas, que si bien no son complicados de resolver, 
provocan que el directorio se este expandiendo muchas veces, lo que puede derivar en un directorio demasiado grande y difícil 
de operar (y posiblemente la generando la necesidad de mantenerlo persistido ya que no cabe en memoria).


\subsubsection{Algoritmo de $Hashing$}

En este tp se usa un Hash llamado SHA-1(cuya salida es de 20 bytes), 

Para la implementación se uso el pseudo-código que provee wikipedia\cite{SHA1}.

La clase EstrategiaHashSHA1 es una clase de servicio (es decir, no tiene estado) que calcula el
algoritmo de SHA-1.
La función recibe un string con los bytes a procesar, y devuelve un string con el hash. Tambien hay un argumento opcional booleano
que indica si se desea obtener la salida en binario o en hexadecimal. Para poder explicar que las diferencias entre las dos salidas, primero hay que entender
que el algoritmo funciona de manera tal, que al procesar la entrada, en algun momento se llega al resultado, que son 5 ints. La diferencia de las dos salidas consiste
en como se muestra la información de esos enteros. Si se setea la opción hexa-decimal, se devuelve el contenido de memoria(en big endian) de cada variable en
formato hexadecimal, concatenadas. En cambio si se setea la opción binaria, se devuelve un casteo de los ints a un string(en big endian).

\subsubsection{Beneficios de la correcta selección del algoritmo de $Hashing$}
Las grandes ventajas que trae la utilización de un indice de $hashing$ extensible se ven completamente opacadas si la elección 
del algoritmo de $hashing$ es desacertada. Si este fuera el caso, provocaría un aglomeramiento de las claves almacenadas en el 
indice de forma tal que la división de las cubas del indice y las expansiones del directorio sean mucho mas frecuentes de lo 
necesario. La selección del algoritmo de $hashing$ SHA-1 nos garantiza que en casos generales esta aglomeración no existirá ya 
que las claves se distribuirán uniformemente en todos las cubas. Esto se logra gracias a la gran aleatoriedad de los $hashes$ 
de claves que se obtienen, permitiéndonos utilizar uniformemente todo el directorio.

\subsubsection{Diseño e implementación}

\begin{figure}[h]
\centering
\includegraphics[scale=0.35]{img/Hashing/Indice_hash_Extensible_v3.png}
\caption{IndiceHashExtensible.}
\label{cod_Indice_Hash_Extensible_UML}
\end{figure}

El indice hash extensible utiliza cubas donde almacena un string que representa la clave del
usuario hasheada y un entero que representa la posición donde se
encuentra el bloque que contiene el dato del usuario. El tamaño de la cuba
debe tener en cuenta dos aspectos importantes, por un lado debe permitir una
lectura rápida y por otro lado debe ser lo suficientemente grande para que
entren una cantidad considerable de datos y de esta forma evitar continuos
desbordes en estas. Las cubas poseen el atributo $profundidad$, el cual es
necesario para poder compararlo con la profundidad del directorio y decidir si
en el caso de una división es necesario la expansión del directorio y para poder determinar
como realizar la división de las claves.

Se decidió que el directorio se encuentre en memoria durante la vida del índice por
$Hashing$ extensible. Esta decisión se tomo por varios motivos:

\begin{itemize}
\item El tamaño del directorio en memoria es razonablemente pequeño.
\item El directorio sufre de sucesivas expansiones y contracciones las cuales
empeorarían la performance del hash extensible considerablemente.
\item Se reduce en $1$ la cantidad de accesos a disco para encontrar una dato.   
\end{itemize}

Para la implementación del directorio se creo la clase $Directorio$ la cual
trabaja con un vector de $stl$ el cual se persiste en el
momento en que la instancia del indice hash extensible se destruye,
permitiendo que se recupere luego.


\ \\
\begin{figure}[h!]
\centering
\lstinputlisting{src/IndiceHashExtensible.h}
\caption{IndiceHashExtensible.}
\label{cod_Indice_Hash_Extensible}
\end{figure}

A continuación se detallan un diagrama UML del $IndiceHashExtensible$ en la figura \ref{cod_Indice_Hash_Extensible_UML} y los métodos mas importantes del mismo, enumerados en la figura \ref{cod_Indice_Hash_Extensible}:



\begin{itemize}

\item Insertar:
El objetivo de este método es insertar una clave del usuario y una posición de almacenamiento donde esta persistido el dato 
asociado a esta clave. Esto se logra obteniendo el $hash$ de la clave pasada por parámetro y consultando en el directorio
 la dirección de la cuba que debería contener la clave que se insertara. Hecho esto, se accede a la cuba en cuestión, y si 
tiene suficiente lugar disponible para insertar el nuevo par clave-posición, lo inserta en la cuba y la persiste. Si la cuba 
en cuestión no tuviera suficiente lugar sera necesario dividir la cuba. Dado que los registros de las cubas están desordenados, 
sera necesario comparar uno por uno los $hashes$ de cada par clave-posición para determinar, acorde a la profundidad de la cuba, 
a cual de las cubas resultantes se moverá cada registro. Luego sera necesario actualizar el directorio para que contenga las 
direcciones de almacenamiento de ambas cubas, en la posición adecuada. Para esto, habrá que analizar si es necesario expandir 
el directorio o no; si la cuba que se acaba de dividir tiene distinta profundidad que el directorio, implica que existe mas de 
una referencia de esta cuba en el directorio y por lo tanto se podrá direccionar alguna de estas referencias sobrantes a la 
nueva cuba resultante. De otra manera, sera necesario expandir el directorio duplicando todas las referencias de este a cada 
cuba excepto las referencias a la cuba que se acaba de dividir. Estas ultimas serán repartidas entre la cuba original y la 
nueva cuba, de acuerdo a las direcciones resultantes de los $hashes$ calculados. Finalmente, este método devuelve void ya que 
asume que la inserción del par clave-posición siempre cabe en el almacenamiento.

\item Buscar: El método buscar se encarga de devolver la posición relativa del
bloque en el que se encuentra el dato cuya clave es la clave pasada por el
usuario. El método buscar comienza calculando la dirección de la cuba donde se debería
encontrar la clave a través del método $crearDireccion$, el cual devuelve una
posición del directorio que contiene la posición en el almacenamiento de la
cuba a hidratar. Una vez hidratada la Cuba, se busca dentro de esta para ver
si se encuentra la clave buscada, en el caso de que se encuentre el método
devuelve true y devuelve la dirección del dato modificando el argumento pasado
por parámetro.

\item Eliminar: El objetivo del método es eliminar una clave indexada y su
posición asociada del indice.  El método comienza buscando la cuba donde debería encontrarse
la clave a eliminar y le pide a esta que elimine la respectiva clave. Si la
clave no se encuentra en la cuba, el método eliminar devuelve false. En el
caso caso, dado que el tamaño de la cuba se reduce, se intenta combinarla con
otra cuba. Para poder combinar las cubas, ambas deben tener la misma
profundidad que el directorio y deben tener el suficiente espacio libre para
poder guardar todos los datos de la otra cuba. En el caso de que la cuba se
haya podido combinar, se intenta contraer el directorio y en caso de que se
logre se intenta combinar de nuevo de forma recursiva, eliminando en cada
llamada las cubas que fueron absorbidas por otras. Luego de intentar combinar
se persiste la cuba.

\item CrearDireccion: Dado una clave, el método se encarga de devolver la
posición del directorio que cuyo contenido es la posición relativa de la cuba
donde se debería encontrar la clave. Esto lo hace a través del
uso de un algoritmo de hashing sobre la serialización de la clave del usuario.
Crear dirección usa la política de utilizar los bits sufijos del resultado del
hashing, dado que estos en general se distribuyen de manera mas uniforme
permitiendo que las claves se distribuyan también de manera uniforme.

\end{itemize}

Por otro lado, los métodos mas importantes de la clase Directorio son:

\begin{itemize}

\item Expandir: El método es necesario cuando alguna cuba necesita dividirse y
su profundidad es igual que la del directorio. Lo que hace el método es
duplicar el tamaño del directorio, y hacer que cada cuba sea apuntada por el
doble cantidad de direcciones de directorio que antes.

\item Contraer: El método es necesario cuando alguna cuba se combina y todas
las cubas están siendo apuntadas por 2 direcciones del directorio como mínimo.
Lo que hace el método es disminuir el tamaño del directorio a la mitad y hace
que cada cuba sea apuntada por la mitad de las direcciones que antes.


\end{itemize}



\subsection{Indice en Arbol B\#}
Los arboles B\# son una variante de los arboles B+, siendo estos a su vez una implementacion de los arboles B. En otras palabras, para comprender la base teorica estos arboles debemos introducirnos en el concepto de arbol B.

%Lo q sigue esta COPIADO de la wikipedia
La idea tras los árboles-B es que los nodos internos deben tener un número variable de nodos hijo dentro de un rango predefinido. Cuando se inserta o se elimina un dato de la estructura, la cantidad de nodos hijo varía dentro de un nodo. Para que siga manteniéndose el número de nodos dentro del rango predefinido, los nodos internos se juntan o se parten. Dado que se permite un rango variable de nodos hijo, los árboles-B no necesitan rebalancearse tan frecuentemente como los árboles binarios de búsqueda auto-balanceables, pero por otro lado pueden desperdiciar memoria, porque los nodos no permanecen totalmente ocupados. Los límites superior e inferior en el número de nodos hijo son definidos para cada implementación en particular. Por ejemplo, en un árbol-B 2-3, cada nodo sólo puede tener 2 ó 3 nodos hijo.
Un árbol-B se mantiene balanceado porque requiere que todos los nodos hoja se encuentren a la misma altura.

Los árboles B tienen ventajas sustanciales sobre otras implementaciones cuando el tiempo de acceso a los nodos excede al tiempo de acceso entre nodos. Este caso se da usualmente cuando los nodos se encuentran en dispositivos de almacenamiento secundario como los discos rígidos. Al maximizar el número de nodos hijo de cada nodo interno, la altura del árbol decrece, las operaciones para balancearlo se reducen, y aumenta la eficiencia. Usualmente este valor se coloca de forma tal que cada nodo ocupe un bloque de disco, o un tamaño análogo en el dispositivo.
%hasta aca esta COPIADO de la wikipedia

Basandose en lo anterior, el arbol B+ es una variacion del arbol B en la que los datos son solo guardados en los nodos hoja, reservandose el resto de los nodos para guardar referencias a las hojas o a otros nodos. Se denomina frecuentemente a estos nodos, "nodos indice" y conforman un "indice B" a las hojas, ya que su funcion es unicamente proveer las referencias para encontrar a los nodos hoja.

Finalmente, el arbol B\# es una pequeña variacion del B+, donde los mecanismos de insercion y supresion son modificados de forma tal de garantizar que todos los nodos queden siempre completos en al menos 2/3 de su capacidad, en vez de a la mitad de su capacidad como ocurria con los arboles-B o B+. Esto se logra evitando que cuando un nodo se llene indefectiblemente genere un nodo nuevo, intentando primero balancear sus claves con alguno de sus hermanos. Si a pesar de esta estrategia, los nodos se ven de todas formas rebalsados, entonces se generara un nuevo nodo con el cual los dos nodos rebalsados distribuyen sus claves, logrando que los nodos queden siempre en al menos 2/3 de su capacidad.


% hay q intentar explicar como funcionan las rotaciones y demas mecanica de estos arboles, igual q se hizo con el indice hashing.

\subsubsection{Estructura de la organización B\#}

\begin{figure}[htb]
\centering
\includegraphics[scale=0.2]{img/BSharp/B+tree.png}
\caption{Arbol B+ Elemental}
\label{cod_Arbol_B_Elemental}
\end{figure}

El arbol-B\# al igual que cualquier arbol-B es un arbol n-ario, es decir que en cada nodo tendremos referencias a multiples nodos asociados a este nodo (figura \ref{cod_Arbol_B_Elemental}). A su vez, las claves dentro de cada nodo se guardara ordenada, y todos los nodos no hoja (nodos indice) tendran para cada clave una referencia a otro nodo que contenga claves menores que esta ultima, pero mayores a la clave anterior a esta. Bajo esta premisa de orden, las busquedas en esta clase de arboles se pueden realizar con pocas iteraciones, y en nuestro, con pocos accesos a disco si los nodos no estuvieran en $buffer$.

Sin embargo, mantener este orden para sucesivas inserciones y eliminaciones de datos no es trivial. En caso de insertar una clave en un nodo que provoque que este $overflow$, se intentara un balanceo entre el nodo actual y alguno de sus hermanos. De no ser posible esto por que sus hermanos quedarian tambien rebalsados, entonces se procede a una division "2 en 3", es decir, generar un nuevo nodo con el cual los 2 originales se distribuiran las claves y referencias. Como estamos trabajando con claves variables, esta operacion podria provocar un $underflow$, que debera ser resuelto inmediatamente despues de esta operacion.

La operacion inversa, la eliminacion de una clave, puede generar el caso inverso, es decir el $underflow$. Esto ocurre cuando la eliminacion de la clave en cuestion del nodo, provoca que el nodo quede en menos de los 2/3 de su capacidad, haciendo necesario un rebalanceo. Este rebalanceo se intenta hacer, pero podria no ser posible ya que los hermanos podrian quedar en underflow tambien. En este caso se intentao condensar 3 nodos en 2, aunque para esto es requisito que el nodo en cuestion tenga al menos 2 hermanos y ademas el tamaño de las claves de los nodos no deben ser demasiado dispares para permitir una correcta distribucion de las claves. Si ni siquiera esto es posible de realizar, la unica alternativa que queda es simplemente dejar todo como esta, y dejar el nodo original en underflow, situacion que es priorizada antes q cualquier otra ya q simlpemente estariamos en el caso de un arbol B tradicional. No se debe olvidar que luego de todas estas operaciones, es necesario actualizar la infromacion del nodo padre para que refleje los cambios.

Finalmente, es necesario considerar los casos especiales que involucran al nodo raiz, ya que en esta caso particular, este nodo no tiene hermanos con quien balancear sus datos. Para resolver esta situacion particular, se permite que la raiz pueda llegar hasta 4/3 de su capacidad, es decir, mantenerse en un estado de $overflow$ hasta los 4/3 de su capacidad. Gracias a esto, cuando la raiz exceda los 4/3 de su capacidad original, simplemente se la divide en 2, realizando una division como cualquier arbol-B o B+ tradicional.

\subsubsection{Diagrama UML del Indice B\#}

\begin{figure}[htb!]
\centering
\includegraphics[scale=0.4]{img/BSharp/Diagrama_Indice_BSharp.png}
\caption{Diagrama UML del Indice B\#}
\label{cod_Arbol_B}
\end{figure}

En la figura \ref{cod_Arbol_B} se puede ver el diagrama UML de clases del arbol B\#




\subsubsection{Inconvenientes de un árbol de claves de longitud variable}
La posibilidad de utilizar claves de longitud variable dentro de los nodos del arbol B\# implica varias situaciones problematicas que no existirian de otra manera. La primera de ellas, y la mas evidente, es que al no poder controlar la relacion entre el tamaño del bloque y la cantidad de claves que caben en él, la division tajante del minimo de 2/3 de capacidad completa en todo momento es mas dificil de mantener, especialmente si el tamaño de los nodos es relativamente pequeño en comparacion al tamaño promedio de las calves que se desea almacenar. Otro problema, menos evidente pero mucho mas grave, es que a diferencia de los arboles-b predecesores, ahora una simple actualizacion de datos puede generar un $overflow$, o un $underflow$, generando la necesidad de contemplar estas nueva posibilidades.

A pesar de esto, se puede sacar provecho a esta situacion adversa. Al existir claves de distinto tamaño, implica que algunas claves seran mas chicas que otras. Dado que nuestra unidad de informacion es la clave, el hecho de que estas sean mas chicas deriva en que podremos tener mas cantidad de claves como esta en un nodo, situacion que nos conviene dado que nos permitira direccionar a mayor cantidad de nodos. Por esto, podriamos modificar el algoritmo de balanceo de nodos de forma tal que las claves chicas sean "promovidas" a nodos superiores del arbol, que tendra como consecuencia una disminucion en la altura del arbol y por ello una disminucion en la cantidad de iteraciones necesarias para encontrar la clave buscada.

% Verificar q lo anterior sea correcto
%es muy dificil darle al 2/3
%update puede causar overflow o underflow


% ahblar sobre el borrado logico y el borrado "fisico" (por ej cuando borras un bloque de del archivo, es un borrado logico y si lees el contenido del archivo podria parecer q se repite la info)

\section{Escritura Diferida}
Una de las variantes de EstrategiaRecurso, EstrategiaRecursoEscriuraDiferida, administra los dos almacenamientos del recurso, en forma análoga al caché buffer de linux\cite{bufferCache}.
En líneas generales se trata de priorizar el trabajo sobre el buffer en memoria, de tamaño limitado, y realizar la actualización de información al disco en forma esporádica, y de un mayor número
de elementos por vez. De esta forma se optimiza por un lado el costo de las operaciones puesto que se trabaja siempre en memoria, y se reducen los accesos al disco, fuentes del mayor overhead
en el manejo de datos.

Ya que la cantidad de unidades de almacenamiento que puede mantenerse en el buffer en un momento dado está limitada por el tamaño de éste, se aplica una política de \emph{least recently used}(LRU)\cite{cacheAlgorithms} para definir cuáles son los que se guardan allí, esto es, se mantienen en el cache los elementos usados más recientemente, que de acuerdo al principio de localidad son los que más probablemente se necesitarán a continuación. Para implementar esa política se traa a los elementos del buffer como a una lista enlazada, ordenada de manera que los elementos usados recientemente
estén el cabeza de la lista. A si mismo se necesta una estructura para llevar cuenta de los espacios vacíos que puedan generarse en ese buffer.

Para integrar al Toolkit esas estructuras de manera transparente, se creó una implementación del Wrapper de Componente que indica la posición en el Buffer de los elementos anterio y siguiente
de la lista. Adicionalmente se guardan en el wrapper la posición de ese elemento en el archivo, y si un \emph{dirty bit} para saber si ha sido alterado desde la última vez qu se lo grabó en el 
disco. La lista de espacios no es más que aquella que administra cada almacenamiento para control de la fragmentación externa(\ref{s_frag_ext}).

Cada alta, baja y modificación de datos se realiza exclusivamete en el buffer; cuando se necesita usar una unidad que no está presente en la lista, se lo incluye como su primer elmento, 
bajando a disco el úlimo de ser necesario. Más allá de ese \emph{flushing} individual cuando se necesita lugar en el buffer, se realiza un \emph{flushing} masivo de buffer a disco, 
actualizando todos los elementos que fueron modificados respecto a su versión almacenada (o que aún no han sido guardados por primera vez). Este proceso masivo se realiza cada vez que 
se destruye el recurso de almacenamiento.

Cuando se trabaja con índices, como los elementos nuevos no se guardan en disco inmediatamente, en general se posterga su indexación al momento en que se realiza su \emph{flushing}.


\section{Compresión}
\label{compresion}

\subsection{Integración al Toolkit}
El proceso de integración al Toolkit de la alternativa de componentes comprimidos, fue prácticamente inmediato, dada la separación de incumbencias con que diseñaron las entidades anteriores.
La compresión no es más que un procesamiento extra, posterior a la serialización de un elemento, así como la descompresión a la hidratación del mismo. Así, alcanzó con extender el componente
Bloque a BloqueCompresor, encargado de realizar estas nuevas tareas.

Se adaptó, a su vez, la EstrategiaAlmacenamientoBloques, para que realice la instanciación de bloques o bloques compresores, de manera transparente, a trvés de un \emph{factory method} \cite{gof95}.
Por último, dado que el tamaño de la serialización de un bloque compresor tras agregar un nuevo elemento no puede predecirse sin agregarlo, se agregó un método para realizar esa predicción, 
y se adaptaron los controles de fragmentación interna para qu tengan en cuenta este nuevo comportamiento.


\subsection{Algoritmo de Compresión}
El algoritmo de compresion implementado es un aritmetico dinamico de orden 1, simbolos de 8 bit y un tamaño de direcciones de 32 bits. Que sea de orden 1 indica la utilización de contextos, el número de
orden indica la cantidad de caracteres precedentes que se toman para predecir. La idea de los contextos se
basa en que los textos tienen secuencias que se repiten, y por lo tanto es
plausible predecir el símbolo siguiente a partir de los símbolos precedentes.
Para calcular la estadistica de los simbolos se cuenta con 256 tablas de 256 simbolos cada una, permitiendonos esto evaluar un contexto de orden 1. Sin embargo, buscando una
optimizacion de memoria, estas tablas no son creadas en memoria hasta que son utilizadas por primera vez, obteniendo mejoras en casos frecuentes de
compresion de textos ascii, donde no se utilizan todos los simbolos posibles.
A diferencia del Aritmético Estático que lee dos veces el archivo, una para
contar las apariciones y otra para comprimir, el aritmético dinámico lo hace
todo en una lectura por lo cual su tabla de frecuencia se inicializa con todos los
símbolos en 1. La ventaja del dinámico es por un lado la velocidad, no es necesario hacer
dos lecturas sobre el archivo, y otra ventaja que posee es que no necesita
adjuntar al resultado de la compresión la tabla de frecuencias.

Para el trabajo práctico se utilizó la aritmética de enteros con 32 bits de
precisión, por lo cual el techo inicial vale $2^{32} -1$ y el piso inicial vale 
$0$. Este techo y piso varia de acuerdo al ultimo símbolo leído, de acuerdo al
siguiente calculo:

\begin{verbatim}
rango = techo - piso + 1
nuevoPiso = pisoActual + rango * P(n - 1)
nuevoTecho = pisoActual + rango * P(n) - 1
\end{verbatim}

Donde $P(n)$ es la probabilidad de que de que aparezca algún
símbolo desde el ascii $0$ hasta el leído, mientras que $P(n - 1)$ es la probabilidad de que aparezca algún símbolo
desde el ascii $0$ hasta al símbolo anterior al leído.  

Una vez calculado el piso y el techo, se deben normalizar. El proceso de
normalización consiste en la detección y el tratamiento de overflow y
underflow.

Si tanto el piso como el techo comparten los bits mas significativos, estos se eliminan tanto del
techo como del piso. Los bits menos significativos del techo se completan con
unos mientras que en el piso se completan con ceros. Estos bits eliminados se
agregan a la emisión final, es decir que pasan a formar parte de la compresión
final. Por ejemplo el techo $11100100$ y el piso $11101100$ comparten los
primeros cuatro bits ($1110$), por lo tanto luego de normalizar, el techo
quedara $01001111$ y el piso quedara $11000000$.  

Por otro lado, si el piso tiene la forma de $01...$ y el techo la forma de 
$10...$ existe un underflow y se trata eliminando los bits a partir del
segundo mas significativo y rellenando los bits menos significativos de la
misma forma que sucede con los overflow. Por ejemplo si tenemos el techo $10011010$ y el
piso $01110001$, al eliminar el segundo y el tercer bit de cada uno, el piso
quedaría $01000100$ y el techo $11101011$.

Debido a que estamos trabajando con un algoritmo de compresion dinamico, el proceso de descompresion sera muy similar al anterior, ya que es necesario ir reconstruyendo la informacion estadistica a medida que se descomprime la informacion. Las tablas de frecuencias se inicializaran tomando las mismas suposiciones que al comprimir, para mantener una consistencia, y se leeran los primeros 32 bits de informacion comprimida (que es el minimo tamaño de informacion comprimida posible). A estos 32 bits los llamaremos $ventana$ y la reutilizaremos progresivamente a lo largo de la ejecucion del algoritmo.

Pasada esta primer etapa, se realizaran iterativamente los siguientes pasos:
\begin{itemize}
\item Buscamos entre que rango de direcciones se encuentra la ventana analizada, y el simbolo asociado a este rango.
\item Encontrado el simbolo, se normaliza el nuevo piso y el nuevo techo, a partir de los rangos anteriores, y se los guarda como el piso y techo actual.
\item Calculamos el $Overflow$ y $Underflow$ resultantes de la normalizacion anterior y guardamos las cantidades de bits procesadas en cada caso.
\item Modificamos la $ventana$ anterior, eliminando los bits que resultaron del $Overflow$ y $Underflow$ anterior.
\item Si no hemos llegado al final de los datos comprimidos, cargamos la ventana con mas datos nuevos, y repetimos el proceso.
\end{itemize}

\subsection{Diseño e implementación}

\begin{figure}[htb]
\centering
\includegraphics[scale=0.5]{img/Aritmetico/Aritmetico_UML.png}
\caption{Diagrama UML del Compresor Aritmetico}
\label{cod_UML_Aritmetico}
\end{figure}

En la figura \ref{cod_Arbol_B} se puede ver el diagrama UML de clases del arbol B\#

El diseño del aritmético se baso en 5 clases que cooperan entre si para llevar
a cabo en forma exitosa el algoritmo de compresión y descompresión. Las clases
utilizadas son: $BloqueCompresor$, $CompresorAritmetico$, $ManejadorBits$, 
$TablaDeFrecuencias$ y $Contexto$.

La clase $BloqueCompresor$ es la encargada de llamar al Algoritmo de
compresión y descompresión cuando es necesario. Algunos de sus métodos son:

\begin{itemize}
\item agregar: El método intenta agregar un componente al bloque, en caso de
que no haya suficiente espacio para agregarlo tira la excepción 
$DesbordeDeBloqueException$. Para saber si hay suficiente espacio para agregar
el componente se serializa y se verifica que el tamaño de la serialización sea
menor al espacio libre del bloque.
\item serializar: Llama al método serializar de la clase base, y al resultado
de la serialización se le aplica el método comprimir del singleton de la clase
$CompresorAritmetico$.  
\item hidratar: A través de la instancia de $CompresorAritmetico$ se llama al
método descomprimir sobre el stringstream a deshidratar y luego se llama al
método deshidratar de la clase Base sobre el stringstream descomprimido.
\end{itemize}

La clase $CompresorAritmetico$ es la que contiene toda la lógica del algoritmo de
compresión y de descompresión. Esta clase fue implementada como un $singleton$ dado que
cada compresión o descompresión es independiente de la anterior y por lo tanto
solo es necesaria una sola instancia en todo el programa. Algunos de sus
métodos son:

\begin{itemize}
\item comprimir: Dado un string a comprimir, devuelve el string comprimido que
produce. Para llevar a cabo este proceso, el método recorre uno a uno todos los
caracteres del string exceptuando el último y llama al método $comprimirCaracter$. El método 
$comprimirCaracter$ calcula el nuevo techo y el nuevo piso a través de la
función $calcularRango$, luego llama al manejador de bits para que los
normalice y luego aumenta la cantidad de apariciones del símbolo en
la tabla de frecuencias.
El último símbolo tiene un tratamiento especial, primero se calcula el techo y
el piso para este símbolo y luego se emite todo el piso.

\item descomprimir: Dado un string comprimido con su respectivo padding, devuelve el string con los simbolos descomprimidos.
El metodo setea las variables iniciales de forma que sean coherentes con la compresion, y recorre iterativamente los bits comprimidos utilizando los metodos $buscarSimbolo$ para encontrar el proximo simbolo a descomprimir y $descomprimirCaracter$ que es similar al proceso de compresion, calculando $Overflows$ y $Underflows$ de las emisiones para conocer la cantidad de bits emitidos para cada simbolo. Finalmente utiliza los metodos $compactarVentana$ y $cargarVentana$ para eliminar los bist ya utilizados, y cargar nuevos, respectivamente.

\item calcularRango: Dado un símbolo, devuelve su piso y su techo. A partir de
las siguientes ecuaciones:

\begin{verbatim}
rango = techo - piso + 1
pisoSimbolo = pisoActual + rango * probabilidadSimboloAnterior
techoSimbolo = pisoActual + (rango * probabilidadSimbolo) - 1
\end{verbatim}

El resultado del piso debe ser redondeado hacia arriba, mientras que el
resultado del techo debe ser redondeado hacia abajo.

El encargado de calcular probabilidadSimboloAnterior y probabilidadSimbolo es
una instancia de la clase $TablaDeFrecuencia$.  

\item buscarSimbolo: Dada una ventana, devuelve el símbolo cuyo techo y piso
contienen la ventana. Por razones de eficiencia, es eligió realizar una
búsqueda binaria entre los 256 símbolos posibles. En cada iteración de la
búsqueda, se calcula el techo y el piso del símbolo elegido y en caso de que
contengan a la ventana, se termina la búsqueda y se devuelve el símbolo, en
caso contrario continua la búsqueda.

\item cargarVentana: Dada una ventana y la cantidad de bits a cargar, este metodo 
lee del string comprimido tantos bytes como sean necesarios, y los agrega al final 
de la ventana pasada por parametro.
\end{itemize}


Para no dejar toda la responsabilidad en la clase $CompresorAritmetico$, se
encapsulo parte del algoritmo en las clases $ManejadorBits$ y 
$TablaDeFrecuencias$ a las cuales la clase $CompresorAritmetico$ le delega
tareas.  

La clase $ManejadorBits$ es la encargada de realizar todo el trabajo a bajo
nivel. Sus principales métodos son:

\begin{itemize}
\item procesar: Este método es en encargado de normalizar el techo y el piso
del compresor aritmético. Su principal tarea consiste en solucionar los
posibles overflows y underflows que pueden contener el techo y el piso para
luego devolver los valores normalizados. A través del manejo de overflow, se
va creando la emisión final paso a paso. 
\item getEmision: Devuelve un string que es emisión final con el padding
incluido. 
\item compactarVentana: Dada una ventana, la compacta de acuerdo a la cantidad
de overflows y underflows que se produjeron procesando el último símbolo.
\end{itemize}

La clase $TablaDeFrecuencias$ es un contenedor de instancias de la clase 
$Contexto$, y delega todo su trabajo a los contextos que contiene. A su vez,
es el encargado de conocer el contexto Actual. La clase $Contexto$ es la
encargada de mantener actualizada la cantidad de apariciones de cada símbolo y
a su vez es la encargada de calcular la probabilidad de aparición de cada
símbolo que contiene.

Se agrego una optimización a $contexto$ para que solo cree el vector de
apariciones en caso de ser utilizado. Esto permite ahorrar
memoria, dado que en general solo se utiliza $\frac{1}{5}$ del total de los
caracteres ascii.

Los metodos mas importantes de la clase $Contexto$ son:

\begin{itemize}
\item AumentarFrecuencia: Por razones de eficiencia, se eligio que cada
caracter del $vectorApariciones$ tenga precalculada la suma de todas las
apariciones de los símbolos anteriores y la suya. Es decir que al aumentar la frecuencia del caracter $n$ debe
aumentarse en 1 las cantidades de apariciones de los caracteres 
$n+1, n+2, \cdots, 256$. 

\item calcularProbabilidad: Dado un simbolo, devuelve la probabilidad del
simbolo pasado por parametro y del simbolo anterior a este. Esto se realiza a
traves del siguiente calculo:

\begin{verbatim}
probabilidadSimbolo = vectorApariciones[simbolo] / sumaTotalApariciones
probabilidadSimboloAnterior = vectorApariciones[simbolo - 1] / sumaTotalApariciones
\end{verbatim}

Este calculo es tan sencillo dado que $aumentarFrecuencia$ precalcula todo lo
necesario y lo guarda en el $vectorApariciones$.  
\end{itemize}


\section{Pruebas}

Con la aplicación se incluye un set de pruebas (en el módulo ``test/PruebaToolkit.h'') demostrando su funcionalidad básica tanto en manejo masivo de 
datos como en tratamiento de datos particulares.

Usando las clases Alumno y ClaveAlumno descriptas en secciones anteriores, se prueba la carga masiva (sin control de unicidad),
 busqueda y eliminación de rangos de datos, así como altas, bajas y modificaciones de alumnos particulares, para distintas
 configuraciones de recursos de almacenamiento. Adicionalmente, cada recurso persistente se cierra y reabre, 
 para continuar las operaciones.

\section{Conclusiones}
%En la planificacion de este $toolkit$ se evidencio la enorme cantidad de casos a contemplar al generar y utilizar indices $hashing$ o de arboles-B, lo que demoro mucho su implementacion. A pesar de esto, durante la implementacion del mismo surgieron muchos mas casos que los previstos, demostrando que la correcta y completa implementacion de estos sistemas no es tarea trivial.

Por otro lado, muchos de los problemas que surgieron fueron provocados por la syntaxis poco intuitiva de C++. La necesidad de manejar la memoria dinamica, manejar y castear constantemente los punteros, etc, derivaron en un tiempo de debuging demasiado extenso.

Finalmente, se verifico la diferencia de velocidades al acceso de la informacion entre la busqueda secuencial y la utilizacion de indices, demostrando que al manejar grandes cantidades de informacion se torna indispensable el uso de estos ultimos.

\clearpage
\addcontentsline{toc}{section}{Referencias}
\begin{thebibliography}{50}

\bibitem{folk98}Michael J. Folk, Bill Zoellick, and Greg Riccardi.
\emph{File Structures: An Object-Oriented Approach with C++}.
Addison-Wesley, 1998.

\bibitem{gof95}Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides.
\emph{Design Patterns: Elements of Reusable Object-Oriented Software}.
Addison-Wesley, 1995.

\bibitem{iostreams}C++ IOstream Library. http://www.cplusplus.com/reference/iostream/

\bibitem{clone}What is a ``virtual constructor''? 
http://www.parashift.com/c++-faq-lite/virtual-functions.html\#faq-20.8

\bibitem{SolarisZFS}Sun Releases New Update for Solaris 10 Operating System.
http://www.sun.com/aboutsun/pr/2009-10/sunflash.20091008.3.xml

\bibitem{AmigaOS}Idiosyncrasies; The spatial paradox. http://mobile.osnews.com/story.php/21826/sam440ep-AmigaOS-4.1//page3

\bibitem{bufferCache}The buffer cache. http://www.faqs.org/docs/linux\_admin/buffer-cache.html

\bibitem{cacheAlgorithms}cache algorithms. http://en.wikipedia.org/wiki/Cache\_algorithms\#Least\_Recently\_Used

\bibitem{SHA1}SHA-1 pseudocode. http:/en.wikipedia.org/wiki/Sha1\#SHA-1\_pseudocode

\end{thebibliography}
\end{document}

\end{document}
